from stack import Stack

mazefile = open('mazes.txt','r')

sizeLine = mazefile.readline()

while(sizeLine):
	sizeLine = sizeLine.strip() #remove the \n
	width, height = [int(x)for x in sizeLine.split()]
	print("Width = " + str(width))
	print("Height = " + str(height))
	
	start = 0,0
	destination = 0,0
	maze = []
	for  i in range(0, height):
		mazeLine = mazefile.readline().strip()
		maze.append(list(mazeLine))
		for j in range(0,width):
			#find the the starting position  - S
			if mazeLine[j] == 'S':
				start = i,j
			#find the the destination position  - D
			elif mazeLine[j] == 'D':
				destination = i,j		
	#initialize a stack
	moves = Stack()
	#keep track of current direction (1-4)
	currentDirection = 1
	currentLocation = start
	#print(maze[start[0]][start[1]])
	#print(maze[destination])
	#while not currentLocation == destination:
	mazeIsSolvable = True
	while not maze[currentLocation[0]][currentLocation[1]] == 'D' and mazeIsSolvable:
			if (currentDirection == 1 and
				(maze[currentLocation[0]-1][currentLocation[1]] == ' ' or
				maze[currentLocation[0]-1][currentLocation[1]] == 'D')
			):
				moves.push(currentDirection)
				moves.push(currentLocation)
				maze[currentLocation[0]][currentLocation[1]] = 'u'
				currentLocation = currentLocation[0] - 1, currentLocation[1]
				currentDirection = 1
			elif (currentDirection == 2 and
				(maze[currentLocation[0]][currentLocation[1]+1] == ' ' or
				maze[currentLocation[0]][currentLocation[1]+1] == 'D')
			):
				moves.push(currentDirection)
				moves.push(currentLocation)
				maze[currentLocation[0]][currentLocation[1]] = 'r'
				currentLocation = currentLocation[0], currentLocation[1] + 1
				currentDirection = 1
			elif (currentDirection == 3 and
				(maze[currentLocation[0]+1][currentLocation[1]] == ' ' or
				maze[currentLocation[0]+1][currentLocation[1]] == 'D')
			):
				moves.push(currentDirection)
				moves.push(currentLocation)
				maze[currentLocation[0]][currentLocation[1]] = 'd'
				currentLocation = currentLocation[0] + 1, currentLocation[1]
				currentDirection = 1
			elif (currentDirection == 4 and
				(maze[currentLocation[0]][currentLocation[1]-1] == ' ' or
				maze[currentLocation[0]][currentLocation[1]-1] == 'D')
			):
				moves.push(currentDirection)
				moves.push(currentLocation)
				maze[currentLocation[0]][currentLocation[1]] = 'l'
				currentLocation = currentLocation[0], currentLocation[1] - 1
				currentDirection = 1
			elif(currentDirection < 4):
				#if there are more directions to try, turn clockwise
				currentDirection = currentDirection + 1
			else:
				#backtrack
				if not moves.isEmpty():
					maze[currentLocation[0]][currentLocation[1]] = ' '
					currentLocation = moves.pop()
					currentDirection = moves.pop()
					currentDirection = currentDirection + 1	
				elif currentDirection == 4:
					mazeIsSolvable = False
					
	maze[start[0]][start[1]] = 'S'
	solvedMaze = open('mazeSolved.txt','a')
	for row in range(0,height):
		for column in range(0,width):
			solvedMaze.write(maze[row][column])
		solvedMaze.write('\n')
				
	sizeLine = mazefile.readline()